QUICK SORT - Sorting Algorithm With Code

     

QUICK SORT

Quick Sort Is A Type Of Sorting Algorithm. It Is Used To Sort Elements Present In Arrays/Lists. Just Like Merge Sort, Quick Sort Is Also A Divide And Conquer Algorithm. In Quick Sort, We Take A Pivot Element And Place It Such That All The Elements On Left Side Of It Are Smaller And All The Elements On Right Side Of It Are Smaller Than The Pivot Element. Now That The Pivot Element Is Sorted, We Recursively Call The Same Function On Both Left And Right Sub Arrays Leaving The Previous Pivot Element. Pivot Can Be Any Element(First, End Or Middle). In The Example Below, We Take Last Element As The Pivot Element. Although, It Is A Divide And Conquer Algorithm, It Has The Worst Case Complexity Of n^2.

COMPLEXITY

Worst complexity: n^2

Average complexity: n*log(n)

Best complexity: n*log(n)

IMPLEMENTATION

                  C++                           

#include <iostream>
using namespace std;

int Partition(int a[], int low, int high)
{
    int pivot = a[high];
    int i = low-1;
    
    for(int j=low; j<high; j++)
    {
        if(a[j]<pivot)
        {
            i++;
            int temp = a[j];
            a[j] = a[i];
            a[i] = temp;
        }
    }
    
    int temp = a[i+1];
    a[i+1] = a[high];
    a[high] = temp;
    
    return i+1;
    
}

void QuickSort(int a[], int low, int high)
{
    if (low<high)
    {
        int pi = Partition(a,low,high);
        
        QuickSort(a,low,pi-1);
        QuickSort(a,pi+1,high);
    }
}



int main() {
    
    int a[] = {10,7,4,3,8,9,11,10,2};
    int size = sizeof(a)/sizeof(a[0]);
    
    QuickSort(a,0,size-1);
    
    for(int i=0;i<size;i++)
    {
    cout<<a[i]<<endl;
}
    
}

JAVA

public class MyClass {
    
    static int Partition(int a[], int low, int high)
    {
        
        int pivot = a[high];
        int i = low-1;
        
        for(int j=low; j<high; j++)
        {
            if(a[j]<pivot)
            {
                i++;
                int temp = a[j];
                a[j] = a[i];
                a[i] = temp;
            }
        }
        
        int temp = a[i+1];
        a[i+1] = a[high];
        a[high] = temp;
        
        return i+1;
        
    }
    
    static void QuickSort(int a[], int low, int high)
    {
        if(low<high)
        {
        int pi = Partition(a,low,high);
        
        QuickSort(a,low,pi-1);
        QuickSort(a,pi+1,high);
        }
    }
    
    
    static void PrintArray(int a[],int low, int high)
    {
        for(int i:a)
        {
            System.out.println(i);
        }
    }
    
    public static void main(String args[]) {
      int a[] = {10,7,4,3,8,9,11,10,2};
      int size = a.length;
      
      QuickSort(a,0,size-1);
      
      PrintArray(a,0,size-1);
      
    }
}

PYTHON

def Partition(a,low,high):
    pivot = a[high]
    i = low-1
    for j in range(low,high):
        if a[j]<pivot:
            i = i+1
            temp = a[j]
            a[j] = a[i]
            a[i] = temp
    
    temp = a[i+1]
    a[i+1] = a[high]
    a[high] = temp
    
    return i+1
    
def QuickSort(a,low,high):
    if low<high:
        pi = Partition(a,low,high)
        QuickSort(a,low,pi-1)
        QuickSort(a,pi+1,high)
        
def PrintArray(a,high):
    for i in a:
        print(i)

a = [10,7,4,3,8,9,11,10,2]
size = len(a);

QuickSort(a,0,size-1)

PrintArray(a,size-1)